\newcommand{\goal}[1]{\textbf{#1}\\}
\newcommand{\fca}{\textsc{ws}}

\section{Our Model} % (fold)
\label{sec:our_model}
\subsection{Overview} % (fold)
\label{sub:model_overview}
Informally, our network formation model is a game defined by a set of nodes, a value function, and a cost function.
\begin{itemize}
  \item Nodes represent people. Pairs of nodes are given turns in sequence (see section \ref{sub:pairwise_traversal}) to decide whether or not there should be an edge between them. If there is already an edge between them, either node may drop it, but if there is no edge, both nodes must agree for it to be added.
  \item Nodes experience value from their relationships with other nodes: a node gains value whenever it is on some shortest path between two nodes. The value that it gains is inversely proportional to the number of nodes on all shortest paths between those two nodes. (For examples, see section \ref{sub:standard_model}.)
  \item Nodes incur a cost for every edge to which they are incident. We refer to the value that a node gains from its relationships minus the cost of its edges as that node's \emph{utility}.
  \item Nodes are partitioned into subsets called \emph{clusters}. Clusters represent divisions amongst people being modeled; for example, a cluster could consist of all the people who work in the same office, or who speak the same language, or who live in the same city. There is always one ``global'' cluster that includes everyone; this ensures that every node is in at least one cluster with every other node.
\end{itemize}
We are interested in the graphs that result from running this game. Specifically, we focus on the notion of \emph{stability}: a state in which no node has incentive to add or remove any edges.
% subsection model_overview (end)

\subsection{Goals} % (fold)
As we move into the formal description of our model and discussion of possible alternatives, we will judge them by this list of desirable properties.
\label{sub:model_goals}
\begin{enumerate}
	\item \goal{Foster the creation of middlemen.}
	A middleman is a node along a shortest path between two nodes -- call them $a$ and $b$ -- that is neither $a$ nor $b$. Any messages or information traveling between nodes who aren't directly connected must go through middlemen, who are also able to benefit from the information. The middlemen in our model should thus receive some of the value from the $a$--$b$ connection, and $a$ and $b$ should not necessarily be willing to bypass their middlemen and form a direct connection.
	\item \goal{Connect everyone or no one.}
	Because all connections in our model have value, a node should always gain value by making a connection to someone you were not previously connected to. So, unless the cost of having edges within a cluster is set so high that nobody is able to afford one, then edges should form in the cluster such that all nodes are somehow connected to all other nodes (i.e., there is only one connected component within the cluster).
	\item \goal{Show structural holes.}
	A structural hole is some sort of gap between groups of people that makes it harder to maintain a relationship between groups than within either group. These holes can be caused by (for example) physical distance, language barriers, ideological differences, etc. Structural holes should be clearly visible in the edges that nodes choose to create and maintain; there should be many more intra-group than inter-group connections, as long as the hole is sufficiently ``deep'' (i.e., expensive to cross).
\end{enumerate}
% subsection model_goals (end)

\subsection{Clusters} % (fold)
\label{sub:clusters}
Recall that nodes incur a cost for every edge to which they are incident. In our model, a node $a$ experiences a structural hole between it and some other node $b$ by there being a higher cost for having an edge to $b$ than there would be if there were no hole between the two, or if there were a hole that was less ``deep''. 

We define where the structural holes are by organizing the nodes into sets called \emph{clusters}. Each cluster has a cost associated with it. To determine the cost of connecting any two nodes, you simply find all the clusters of which both nodes are members, and use the lowest of the costs associated with those clusters.

As an example, consider a hypothetical company called Worldwide Sprockets (\fca{}). \fca{}'s employees are split into two offices: one in New York and one in London. Each office has people working for \fca{}'s two divisions: engineering and sales. A partial employee roster is given in \autoref{table:wser}.

\begin{table}[H]
\centering
\caption{Worldwide Sprockets' employee roster\label{table:wser}}
\begin{tabular}{llll}
	\toprule
	\multicolumn{2}{c}{London} & \multicolumn{2}{c}{New York} \\
	\cmidrule(r){1-2} \cmidrule(r){3-4}
	Engineering & Sales & Engineering & Sales \\
	\midrule
	Alice & Charles & Emily & Gus \\
	Bob & Doris & Fred & Harriet \\
	\ldots{} & \ldots{} & \ldots{} & \ldots{} \\
	\bottomrule
\end{tabular}
\end{table}

Clusters allow you to capture all of these observations about \fca{}:

\begin{itemize}
	\item It is easiest to be friends with people who work in your division in your city.
	\item It is somewhat less easy to be friends with people who work in your division in the other city.
	\item It is harder to be friends with people who work in the other division in your city.
	\item It is hardest to be friends with people who work in the other division in the other city.
\end{itemize}

First, define clusters for each city-division combination, and associate a low edge cost with them. Then, define a cluster with a higher edge for each division, a cluster with an even higher edge cost for each city, and an overall cluster with the highest edge cost for the entire company.

% subsection clusters (end)

\subsection{Formal Definition} % (fold)
\label{sub:model_formal_definition}
An instance of the network formation game consists of the following:
\begin{itemize}
  \item A set of nodes $V$
  \item A set of $k \ge 1$ clusters of nodes $\allclusters = \{C_1,\ldots,C_k\}$ such that $\forall\,C_i \in \allclusters\,(C_i \subseteq V)$. At least one of the clusters must be equal to $V$ (i.e., one of the clusters must contain every node).
  \item An function $v : V \rightarrow \mathbb{R}$ that gives the value of any node; we define the one that we use in section \ref{sub:standard_model}.
  \item An function $p : \allclusters \rightarrow \mathbb{R}$ that gives the edge cost associated with each cluster.
\end{itemize}

In addition, we define a function $q : \langle{}V,V\rangle{} \rightarrow \mathbb{R}$ that gives the cost of an edge between two nodes, and a function $u : V \rightarrow \mathbb{R}$ that gives the utility of any node.

\begin{align*}
  q(a, b) &= \min_{1 \le i \le k}\left(p(C_i)\ |\ a,b \in C_i\right) \\
  u(a)    &= v(a) - \sum_{b\ \in\ \Gamma(a)} q(a, b)
\end{align*}
% subsection model_formal_definition (end)
% section our_model (end)
